home *** CD-ROM | disk | FTP | other *** search
/ Chip 1996 April / CHIP 1996 aprilis (CD06).zip / CHIP_CD06.ISO / hypertxt.arj / 92 / ORA_ELJ.CD < prev    next >
Text File  |  1995-09-14  |  11KB  |  290 lines
  1.       @VEljuthatunk-e  az órától  Einsteinig, avagy  megfejtések
  2.       áprilistól májusig@N
  3.  
  4.       @VAz óra...@N
  5.  
  6.           Åprilisi számunkban jelent meg  @KAz óra és Einstein@N  címû
  7.       fejtörônk, amelynek lényege,  hogy mikor és  hányszor vannak
  8.       egy hagyományos  (és jól  mûködô) órán  az óramutatók  olyan
  9.       helyzetben,  hogy  felcserélésükkel  egy  másik   lehetséges
  10.       helyzetet (valós, értelmezhetô idôpontot) kapjunk meg.
  11.           A  feladatra  kilenc  megoldás  érkezett,  közülük nyolc
  12.       bizonyult helyesnek.  Megoldóink sokféle  nyelvet használtak
  13.       (Pascal,  Basic,  Clipper,  assembly  stb.),  de  lényegében
  14.       hasonló  utat  jártak végig.  Rövid  matematikai megfontolás
  15.       után  a   ""favágó"  munkát   (azaz  a   keresett  idôpontok
  16.       elôállítását)   a   gépre   bízták.   Az   egyik  lehetséges
  17.       matematikai gondolatmenetet Gáldonyi Béla megoldása  alapján
  18.       foglaljuk össze:
  19.           Ha a kismutató a kiindulási helyzethez képest (ez legyen
  20.       12  óra)  @Kfi@N  szöggel   elfordul,  akkor  a  nagymutató   az
  21.       alaphelyzethez képest @K12*fi@N szöget zár be. A mutatók cseréje
  22.       az  jelenti,  hogy  a  kismutató  szöge  lesz  @K12*fi@N,  míg a
  23.       nagymutató által bezárt  szög @K12*12*fi@N-re változik.  Mármost
  24.       ez  csak  akkor  tekinthetô  cserének,  ha  a  nagymutató új
  25.       helyzete   megegyezik   a  kismutató   régi   állásával.  Ez
  26.       egyenletben így írható le:
  27.           @K144*fi = fi + k*2*pi@N
  28.           ahol a @Kk*2*pi@N  jelzi, hogy a  nagymutató @Kk@N darab  teljes
  29.       kört tett meg közben. Az egyenlet megoldása:
  30.           @Kfi = k/143 * 2*pi@N
  31.           Mivel   a   kismutató   egy   körét   vizsgáljuk   (azaz
  32.       @K0<=fi<2*pi@N), ezért @Kk= 0, 1, 2,  ..., 143@N. Hogy a 12 órát  ne
  33.       számoljuk kétszer, a @Kk@N értékénél el kell hagynunk valamelyik
  34.       határt.  Ezek után  már tényleg  csak a  kulimunka marad:  a
  35.       mellékelt Basic program  (Rákos Péter munkája)  elôállítja a
  36.       keresett idôpontokat.
  37.           A programok  közötti apróbb  különbségeket elsôsorban  a
  38.       kapott  143 megoldás  megjelenítési módja  okozta. Volt  aki
  39.       képernyôre, volt aki nyomtatóra, volt aki file-ba ""terelte"
  40.       a végeredményt.
  41.           E  fordulóban  a szerencse  Gáldonyi  Bélának kedvezett,
  42.       nyereménye egy csomag Tungsram floppy.
  43.  
  44.  
  45.       @VEljutunk-e...@N
  46.  
  47.           Májusi   számunkban  jelent   meg  elôször   ""emeletes"
  48.       rejtvény, a módosított játékszabályoknak megfelelôen.
  49.           A ""földszinti" feladat így hangzott: adott @KN@N település,
  50.       amelyek mindegyikérôl  tudjuk, hogy  melyik másikkal  állnak
  51.       közvetlen   közlekedési   összeköttetésben.   îrjunk   olyan
  52.       programot,  amely  megadja,  hogy  egy  @KA@N   faluból/városból
  53.       eljuthatunk-e egyáltalán egy @KB@N településre.
  54.           Hét  helyes  megoldás  érkezett  határidôre.  A  nyelvek
  55.       nemhivatalos  versenyében  újfent  a  Pascal  nyert, dobogós
  56.       versenytársai a  Prolog és  a Modula  voltak. A  feladat egy
  57.       lehetséges megoldását régi rendszeres megfejtônk,  mondhatni
  58.       szerzônk, Gyombolai Márton részletes dokumentációja  alapján
  59.       vázoljuk.
  60.           Legyen  egy  @Kn*n@N-es logikai  tömbünk  (@KUT@N), amelyben  az
  61.       @K(i,j)@N elem  igaz, ha  van közvetlen  út az  @Ki@N-edik faluból a
  62.       @Kj@N-edikbe,  egyébként hamis.  A kérdés  az, hogy  el  lehet-e
  63.       jutni @Kn1@N-bôl @Kn2@N-be.
  64.           Elsô  lépésben  jelöljük  ki  azt  a  @KH1@N  halmazt, amely
  65.       azokból a falvakból áll, ahová @Kn1@N-bôl egy lépésben el  lehet
  66.       jutni. Ha @Kn2@N benne  van @KH1@N-ben, akkor máris  készen vagyunk.
  67.       Ha  @KH1@N üres  halmaz (@Kn1@N-bôl  sehová nincs  út), akkor  nincs
  68.       megoldás, illetve az a megoldás, hogy nincs út @Kn1@N-bôl @Kn2@N-be.
  69.           Második lépésben azt a  @KH2@N halmazt jelöljük ki,  amelybe
  70.       azok a  falvak tartoznak,  ahová még  nem jutottunk  el (nem
  71.       @KH1@N-beli  és  nem @Kn1@N),  de  @KH1@N-bôl egy  lépésben  elérhetô. A
  72.       @KH2@N-ben így  épp azok  a települések  lesznek, amelyek @Kn1@N-bôl
  73.       pontosan két lépésben érhetôk el. Ha @Kn2@N eleme @KH2@N-nek,  akkor
  74.       készen vagyunk. Ha @KH2@N üres halmaz (vagyis nincs ilyen falu),
  75.       akkor nincs út @Kn2@N-be. És így tovább...
  76.           A  fenti  lépéseket  maximum  @Kn-1@N-ig  tudjuk  folytatni,
  77.       hiszen egy falu csak  egyetlen halmazban lehet benne.  Ha @Kn2@N
  78.       egyiknek sem eleme, akkor nincs út.
  79.           Megfejtônk mellékelt  programjában halmazok  helyett (az
  80.       egyszerûség  kedvéért)  egy  @KLEPES@N  nevû,  @Kn@N  elemû   tömböt
  81.       használ, úgy, hogy  @KLEPES(x)=i@N, ha az  @Kx@N falu a  @KHi@N halmazba
  82.       tartozik. A  @KLEPES@N elnevezést  az indokolja,  hogy @KHi@N elemei
  83.       éppen azok a falvak, ahová @Ki@N lépésben lehet eljutni.
  84.           Fortuna e fordulóban Horváth Sándor barcsi  megfejtônket
  85.       részesítette kegyeiben, övé a doboznyi Tungsram floppy.
  86.  
  87.  
  88.       @VLegrövidebb idô alatt...@N
  89.  
  90.           Az ""emeleti" rejtvény  az elôzô finomításából  adódott:
  91.       az N településrôl  azt is tudjuk,  hogy a meglévô  közvetlen
  92.       összeköttetések  mekkora  menetidôt  jelentenek.  îrjunk egy
  93.       olyan programot, amely megadja a legkisebb idôt igénybe vevô
  94.       utat @KA@N és @KB@N települések között -- ha létezik ilyen.
  95.           A  feladat  e  (némileg  nehezített)  változatára kilenc
  96.       megoldás  érkezett,  többségükben olyanoktól,  akik  az elsô
  97.       variációt  is  megoldották  --  ami  érthetô,  ha figyelembe
  98.       vesszük a két kérdés  rokonságát. Kérdés persze, hogy  kinél
  99.       melyik változat  volt az  elsô, s  adódott esetleg  egyszerû
  100.       melléktermékként a másik megoldás.
  101.           A  szoros  rokonság  okán  folytassuk  Gyombolai  Márton
  102.       gondolatmenetét,  aki  maga  is utal  arra,  hogy  a második
  103.       feladat megoldása jól ráépíthetô  az elsôre. Itt persze  nem
  104.       logikai,  hanem  tényleges  úthosszakat  tartalmazó  integer
  105.       tömböt  kell  használnunk,  -1  értékkel  ott,  ahol   nincs
  106.       közvetlen út.
  107.           A korábbi algoritmusnak az a fô baja, hogy egy  kevesebb
  108.       lépésszámú út hosszabb lehet  egy több lépésesnél. Ezen  úgy
  109.       segíthetünk, hogy egyrészt  nemcsak a lépésszámot  tároljuk,
  110.       hanem  a tömbben  azt is,  hogy az  @Kn1@N-tôl az  @Ki@N-ig  megtett
  111.       távolság  mekkora.  Másrészt a  halmazokat  is másként  kell
  112.       képezni: @KHi@N-be azok a falvak tartoznak, amelyek egyfelôl egy
  113.       @KHi-1@N-beli faluból egy lépésben elérhetôk, és másfelôl
  114.           -- vagy még nem jutottunk el ide (@Khi@N-be) sehogyan
  115.           sem;
  116.           -- vagy most a régi útnál rövidebb úton jutottunk el
  117.           ide.
  118.           Fontos változás, hogy itt  egy @KHi@N-be sorolt falu  késôbb
  119.       átkerülhet  egy @KHj@N  halmazba @K(j>i)@N,  ha rövidebb  (bár  több
  120.       lépéses) utat leltünk. Ezért  nem is állhatunk meg  azonnal,
  121.       amint   eljutunk  @Kn2@N-be,   hiszen  még   rövidebb  utat   is
  122.       találhatunk (@Kn2@N is átkerülhet másik @KH@N halmazba).
  123.           A  változatosság  kedvéért   nem  a  fenti   algoritmust
  124.       megvalósító Pascal  programot közöljük  (melyet az  eddigiek
  125.       alapján   vállalkozó  kedvû   olvasónk  viszonylag   könnyen
  126.       megírhatnak), hanem Déri  Attila Prolog nyelvû  programjának
  127.       fix adatokkal dolgozó változatát. Érdemes tanulmányozni!
  128.           (Emlékeztetôül:  e  kategóriában  most  nem,  hanem majd
  129.       decemberben sorsolunk, rendszeres megoldóink között.)
  130.  
  131.       @KBánhegyesi Zoltán@N
  132.  
  133.  
  134. program vaneut1;
  135. {Gyombolai Márton}
  136.  
  137. var
  138.    i,j,lep,innen,ide,n,n1,n2: integer;
  139.    ures, keszjo: boolean;
  140.    ut: array[1..100,1..100] of boolean;
  141.    lepes: array[1..100] of integer;
  142.  
  143. Procedure Beolvas;
  144. var vane:integer;
  145.  
  146. begin
  147.    write('Faluk száma=');
  148.    readln(n);
  149.    for i:= 2 to n do
  150.      for j:= 1 to i-1 do
  151.      begin
  152.        write(i:3,' és ',j:3, ' közt van út? 1, ha igen, 0, ha nem! ');
  153.        readln(vane);
  154.        ut[i,j] := (vane=1);      {Illenék mindenfélét ellenôrizni,}
  155.        ut[j,i] := (vane=1);      {de itt nem ez a lényeg.}
  156.      end;
  157.    for i:=1 to n do ut[i,i] := false;
  158. end;
  159.  
  160. Procedure Kiir;
  161. begin
  162.    if keszjo
  163.    then writeln('Van megoldás ',lep-1:3,' lépésben!')
  164.    else writeln('NINCS MEGOLDÅS!');
  165. end;
  166.  
  167.  
  168. begin
  169.    Beolvas;
  170.    write('Az induló falu sorszáma: ');
  171.    readln(n1);
  172.    while n1 > 0 do
  173.    begin
  174.      write('A cél-falu sorszáma: ');
  175.      readln(n2);
  176.  
  177.      for i:=1 to n do lepes[i] := -1;
  178.      lepes[n1] := 0;
  179.      keszjo := false;
  180.  
  181.      lep := 1;
  182.      repeat
  183.        ures:= true;
  184.        for innen := 1 to n do
  185.        begin
  186.      if lepes[innen] = lep-1         {Ha INNEN-be az elôzô lépésben }
  187.      then               {jutottunk el         }
  188.        if ut[innen,n2]
  189.        then keszjo := true     {Találtunk utat!    }
  190.        else
  191.          for ide := 1 to n do
  192.            if lepes[ide] = -1       {Ha IDE még nem jutottunk el...}
  193.            then begin
  194.          ures := false;
  195.          if ut[innen,ide]       {...de most igen,     }
  196.          then lepes[ide] := lep;     {akkor ez LEP lépéses út       }
  197.            end;
  198.        end;
  199.  
  200.        lep := lep+1;
  201.      until (lep > n-1) or ures or keszjo;
  202.      Kiir;
  203.  
  204.      write('Az induló falu sorszáma: ');
  205.      readln(n1);
  206.    end;
  207. end.
  208.  
  209.  
  210. CLS
  211. PRINT " FI   ORA   PERC   MASODPERC    ORA    PERC   MASODPERC"
  212. FOR i = 1 TO 143
  213.     fi = i * 12 / 143: a = fi
  214.     h = INT(fi): fi = fi - h: fi = fi * 60
  215.     min = INT(fi): fi = fi - min
  216.     sec = INT(fi * 60): fi = a
  217.     PRINT fi, h
  218.     PRINT "   "; min
  219.     PRINT "   "; sec,
  220.     PRINT "   "; h + 12; "   "; min
  221.     PRINT "   "; sec
  222. NEXT
  223.  
  224.  
  225. /* A lehetô leggyorsabban...?    */
  226. /* Járatok a programban beépítve */
  227. /* Készítette: Déri Attila       */
  228.  
  229. domains
  230.  lista=string*
  231.  
  232. database
  233.  tarol(integer, integer, lista)
  234.  
  235. predicates
  236.  berak(integer, lista)
  237.  ut(lista, string, string, integer)
  238.  kapocs(string, symbol, integer)
  239.  kapcs(string, string, integer)
  240.  nincs(lista, string)
  241.  kiir(lista)
  242.  megnez
  243.  
  244. clauses
  245.  ut(L, X, X, I):-berak(I, [X|L]), !, fail.
  246.  ut(L, X, Y, I):-kapocs(X, Z, K), nincs(L, Z),
  247.          J=I+K, ut([X|L], Z, Y, J).
  248.  
  249.  nincs([], _).
  250.  nincs([X|_], X):-!, fail.
  251.  nincs([_|L], X):-nincs(L, X).
  252.  
  253.  berak(J, L):-tarol(1, I, _), J<I,
  254.           retract(tarol(1, _, _)),
  255.           assert(tarol(1, J, L)).
  256.  
  257.  megnez:-tarol(1, _, []),
  258.      write("Nem talaltam osszekottetest!"), nl, !.
  259.  megnez:-tarol(1, I, L),
  260.      write(I, " idoegyseg alatt megteheto utat talaltam: "),
  261.      kiir(L), write("."), nl,
  262.      retract(tarol(1, _, _)).
  263.  
  264.  kiir([]):-!.
  265.  kiir([X|L]):-L=[], write(X).
  266.  kiir([X|L]):-kiir(L), write(", ", X).
  267.  
  268.  kapocs(X, Y, I):-kapcs(X, Y, I).
  269.  kapocs(X, Y, I):-kapcs(Y, X, I).
  270.  
  271.  kapcs("Baja", "Mohacs", 7).
  272.  kapcs("Baja", "Szekszard", 5).
  273.  kapcs("Mohacs", "Pecs", 6).
  274.  kapcs("Szekszard", "Pecs", 15).
  275.  kapcs("Baja", "Szeged", 9).
  276.  kapcs("Bekescsaba", "Szeged", 9).
  277.  kapcs("Bekescsaba", "Kecskemet", 12).
  278.  kapcs("Kecskemet", "Szeged", 9).
  279.  kapcs("Budapest", "Kecskemet", 8).
  280.  kapcs("Kecskemet", "Baja", 11).
  281.  kapcs("Nagykanizsa", "Szekesfehervar", 13).
  282.  kapcs("Szekesfehervar", "Veszprem", 6).
  283.  kapcs("Veszprem", "Szombathely", 11).
  284.  kapcs("Nagykanizsa", "Szombathely", 11).
  285.  
  286. goal
  287.  assert(tarol(1, 10000, [])), write("Honnan: "),
  288.  readln(X), write("Hova :"), readln(Y),
  289.  ut([], X, Y, 0); megnez.
  290.